The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
In communication systems, the Shannon limit expresses the maximum data speed that can be obtained in a data channel. Shannon's Law states that the highest obtainable error-free data speed is a function of the bandwidth and the signal-to-noise ratio. Error correction coding (ECC) techniques attempt to increase channel performance towards the Shannon limit.
Low-density parity check codes (LDPCs) are ECC codes that allow a channel to have data speeds near the Shannon limit. LDPCs provide coding gain that improves performance. The coding gain can be used for a variety of purposes, such as allowing lower transmit power, higher data throughput, longer transmit distances, and/or increased reliability. When transmit power is limited, the extra coding gain of LDPCs can make the difference between reliable and unreliable communication.
One coding technique that uses LDPCs, referred to as tensor-product code (TPC), incorporates two levels of ECC. A first or inner level protects channel/information bits and employs a single parity check (SPC) code, which appends parity bit to each K data bits. The SPC blocks share redundancy across a sector or memory location. A second or outer level code is the LDPC code, which acts on the parity bits of the inner level. The LDPC code protects the parity bits of the inner level.
An associated decoder for this technique has two stages. A first stage decodes the outer level code and a second stage post processes the result to enforce the SPC parity constraint on the channel bits. This is described in further detail below with respect to FIGS. 1-2.
Referring to FIG. 1, a sample 10-bit SPC code is shown. A non-return-to-zero (NRZ) sector may be subdivided into 10-bit symbols sk(0:9). Symbol length, in general, coincides with Reed-Solomon (RS) error correction coding (ECC) symbol length. To generate an LDPC codeword the bits of each 10-bit symbol are exclusive-OR'd (XOR) together to generate parity bits p, as shown and expressed by equation 1.
                              p          k                =                                            ⊕              9                                      i              =              0                                ⁢                                    s              k                        ⁡                          (              i              )                                                          (        1        )            A collection of user bits form a tensor product codeword if and only if SPC parity bits form an LDPC codeword, i.e. Hp={right arrow over (0)}.
Referring now to FIG. 2, a functional block diagram illustrating a tensor product coded channel system 10 is shown. The system 10 includes a tensor-product code (TPC) encoder 12, a modulator 14, a channel 16, a detector 18, and a TPC decoder 20. A stream of datawords u is encoded by the TPC encoder 12 to provide a stream of codewords c, which may be in the form of binary data. A dataword may refer to a group of binary data, or user bits, suitable for input to an encoder, such as the TPC encoder 12. A codeword may refer to a group of bits generated by an encoder based on an input dataword.
The modulator 14 manipulates the frequency, amplitude, and/or phase of the stream of codewords c to generate a communication/storage signal, such as a transmitted signal w. The transmitted signal w is communicated and/or stored on the channel 16. The channel 16 provides a received signal w′, which may be a corrupted version of the transmitted signal w. The channel 16 may, for example, be a storage medium, such as a magnetic storage medium, an optical storage medium, or an electrical storage medium or other communication channel. The data corruption may be due to noise or interference.
The detector 18 demodulates the received signal w′ and provides an initial estimate signal {circumflex over (r)} of the stream of codewords c. The TPC decoder 20 decodes the initial estimate signal {circumflex over (r)} to recover the stream of datawords u by detecting and/or correcting any errors in the initial estimate signal {circumflex over (r)}. Resultant output of the TPC decoder 20 is estimate signal r.
The TPC encoder 12 includes inner and outer code modules 22, 24, which have corresponding inner and outer codes. The TPC encoder 12 generates the stream of codewords c, which includes the stream of datawords u, as well as redundant bits. The redundant bits provide additional information that can be used by the TPC decoder 20 to detect and/or correct errors in a detected codeword. The inner code module 22 uses the inner code to generate a first set of redundant bits. At least a portion of the first set of redundant bits is further encoded based on the outer code to generate a second set of redundant bits. The first and second set of redundant bits may be concatenated onto the stream of datawords u. The second set of redundant bits may be generated based on the first set of redundant bits.
The TPC decoder 20 includes corresponding inner and outer code modules 26, 28. The inner and outer code modules 26, 28 reverse the encoding performed by the inner and outer code modules 22, 24. Result of the decoding process provides the estimate signal r, which is the same as the stream of datawords u when no errors exist.
With the flexibility of LDPCs, codes can be constructed to match a particular block size or code rate. After the block size and code rate are established, an M-by-N parity check matrix H is constructed and contains a sparse number of ones. The number of rows M is greater than or equal to the number of parity bits N-K, where K is the number of information (user) bits. A binary string c, of length N is said to be a codeword in C if and only if Hc={right arrow over (0)}. An example parity check matrix H where N=7 and K=5 is provided as equation 2.
                    H        =                  [                                                    1                                            1                                            1                                            1                                            1                                            1                                            1                                                                    1                                            0                                            1                                            0                                            1                                            0                                            1                                                                    0                                            1                                            0                                            1                                            0                                            1                                            0                                              ]                                    (        2        )            The LDPC code with the parity check matrix H has, for example, a binary string c=(1, 0, 1, 0, 1, 0, 1)T, which is a codeword in C.
Encoding is done by using equations derived from the H matrix to generate the parity check bits. From the H matrix, the G matrix is evaluated and then used to perform encoding.
Decoding is accomplished using “soft-inputs” with these equations to generate new estimates of the sent values. This process is repeated in an iterative manner resulting in a powerful decoder. The iterative LDPC decoder receives blocks of data, including corrupted bits due to noise, with varying resolution. To decode a block, an iterative process is performed that consists of solving M parity check equations of the H matrix. The confidence levels that the bits in the equations are ones or zeroes is updated using belief propagation or simplified approximations thereof. This is repeated for many iterations. The decoder stops once a valid codeword is found, which satisfies all parity check equations, or when an allotted time has elapsed. Large block sizes and extra iterations improve the performance of the codes, but add to latency, data rate, and memory size issues.